package arrayOps

import C "gitee.com/ljfirst/algo-go-sdk/common/constant"

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/15 17:21
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description
 **/
type PreSumArray struct {
	sumArray []int
}

func (m *PreSumArray) BuildPreSum(array []int) {
	if len(array) == 0 {
		return
	}
	m.sumArray = make([]int, len(array)+1, len(array)+1)
	// attention : 前缀和的数组size比array大1，前缀和的数组从0开始，差分数组从1开始
	for i := 1; i < len(array); i++ {
		m.sumArray[i] = m.sumArray[i-1] + array[i-1]
	}
}

func (m *PreSumArray) QueryPreSum(i, j int) int {
	if i >= len(m.sumArray) || j < 0 {
		return C.ErrorNum
	}
	if i < 0 {
		i = 0
	}
	if j > len(m.sumArray) {
		j = len(m.sumArray)
	}
	return m.sumArray[j+1] - m.sumArray[i]
}

func (m *PreSumArray) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.PreSum},
		Desc: &C.Desc{
			Name:   "PreSumArray",
			NameCn: "前缀和",
			ParamsDesc: map[string]string{
			},
			Example: map[int]string{
				1: "输入数组[1,2,3,4]，计算得到前缀和数组 sumArray[0,1,3,6,10],计算原数组[0,2]的前缀和，只需要计算sumArray[2]-sumArray[0]，即6-0=6",
			},
		},
	}
}
